package com.algorithm.learning.base.二叉树;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/24 22:40
 **/
public class 判断一棵树是否是平衡搜索二叉树 {

    /**
     * 判断一棵树是否是平衡树，每一颗子树，|左树-右树|的高度差 <= 1
     *
     * 这道题的思路如下：
     * 1、要判断整体是否是平衡树，那么首先需要判断左右子树是否是平衡树
     * 2、然后在判断整体的高度差是否小于等于1
     *
     * 所以，我们定义一个Info类，其中属性是 balance:是否平衡,height:当前树的高度
     *
     * 如果左右子树，balance = true，且height差 <= 1，那么整体就是平衡树
     *
     * 可以利用递归来完成左右子树的判断
     *
     * @param root
     * @return
     */
    public static boolean isBalance(TreeNode root) {
        return balance(root).balance;
    }

    private static Info balance(TreeNode root) {
        if (root == null) {
            return new Info(true, 0);
        }
        Info leftInfo = balance(root.left);
        Info rightInfo = balance(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        boolean isBalance = leftInfo.balance && rightInfo.balance && Math.abs(leftInfo.height - rightInfo.height) <= 1;

        return new Info(isBalance, height);
    }

    public static class Info {
        private final boolean balance;
        private final int height;

        public Info(boolean balance, int height) {
            this.balance = balance;
            this.height = height;
        }
    }

    /**
     * 判断一棵树是否是平衡搜索二叉树，
     * 1、首先这棵树需要是平衡树
     * 2、这棵树的所有左子树都要小于根节点，所有右子树都要大于根节点
     *
     * 这道题的思路，与上面判断是否是平衡树是一样的，
     *
     * 我只要返回每个左右子树的最大值和最小值，如果：
     * 根节点的最大值 > 左树的最大值 并且
     * 根节点的最大值 < 右树的最小值
     * 那么这棵树就是搜索二叉树
     * @param root
     * @return
     */
    public static boolean isBalanceSearch(TreeNode root) {
        return isBST(root).isBST;
    }

    private static BstInfo isBST(TreeNode root) {
        // 要注意，这里不能返回0, 0
        // 因为节点值是有可能为负数，如果直接返回0，父节点是负数的话，整体就是错误的
        // 这里直接返回null即可，所以下面的代码，需要注意判空条件
        if (root == null) {
            return null;
        }
        BstInfo leftInfo = isBST(root.left);
        BstInfo rightInfo = isBST(root.right);

        // 先初始化 当前节点的最大值与最小值
        int max = root.value;
        int min = root.value;

        // 这里获取左右子树的最大值最小值，为什么都要与根节点进行比较呢？
        /*
        因为根据递归的特性，当走到叶子节点(没有左右子树)的情况下，这里的max与min就是当前节点值
        当递归往上层方法回调时，其实就是在比较整个树的最大最小值
        所以这里最后的结果一定就是返回，左右子树的最大最小值
         */
        if (leftInfo != null) {
            // 如果左子树不为空，则取最大值与最小值
            max = Math.max(max, leftInfo.max);
            min = Math.min(max, leftInfo.min);
        }
        if (rightInfo != null) {
            // 如果右子树不为空，则取最大值与最小值
            max = Math.max(max, rightInfo.max);
            min = Math.min(max, rightInfo.min);
        }

        boolean isBST = true;
        // 如果左子树，那么这棵树就不是搜索二叉树
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }

        // 如果右子树，那么这棵树就不是搜索二叉树
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }

        // 如果左子树信息为空，那么表示没有左子树，那么肯定是搜索树
        // 如果左子树信息不为空，那么判断，左子树的最大值是否小于根节点
        boolean leftMaxLessRoot = leftInfo == null ? true : leftInfo.max < root.value;

        // 如果右子树信息为空，那么表示没有右子树，那么肯定是搜索树
        // 如果右子树信息不为空，那么判断，右子树的最小值是否大于根节点
        boolean rightMinMoreRoot = rightInfo == null ? true : rightInfo.min > root.value;

        // 只要上面两个条件有一个不成立，那么肯定就不是搜索二叉树
        if (!leftMaxLessRoot || !rightMinMoreRoot) {
            isBST = false;
        }
        return new BstInfo(isBST, max, min);
    }

    public static class BstInfo {
        private final boolean isBST;
        private final int max;
        private final int min;

        public BstInfo(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

}
